package com.lw.leetcode.dp.c;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * c
 * dp
 * 1655. 分配重复整数
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/4 14:55
 */
public class CanDistribute {

    public static void main(String[] args) {
        CanDistribute test = new CanDistribute();

        // false
//        int[] nums = {1, 2, 3, 4};
//        int[] quantity = {2};

        // true
        int[] nums = {1, 2, 3, 3};
        int[] quantity = {2};

        // true
//        int[] nums = {1, 1, 2, 2};
//        int[] quantity = {2, 2};

        // true
//        int[] nums = {420, 420, 420, 235, 687, 420, 420, 591, 759, 420, 420, 420, 326, 756, 420, 376, 420, 989, 387, 212, 420, 89, 420, 420, 326, 420, 420, 420, 387, 387};
//        int[] quantity = {1, 3, 1, 4};

        // true
//        int[] nums = {128, 812, 834, 231, 658, 812, 905, 128, 124, 403, 812, 796, 995, 510, 128, 128, 750, 128, 128, 128, 665, 995, 812, 728, 665, 128, 252, 273, 252, 830, 665, 128, 273, 128, 128, 665, 687, 785, 665, 419, 834, 633, 338, 665, 128, 128, 128, 812, 97, 720, 252, 319, 620, 710, 853, 128, 128, 252, 812, 661, 273, 231, 812, 128, 410, 828, 128, 84, 458, 252, 252, 853, 698, 128, 252};
//        int[] quantity = {15, 7};

        boolean b = test.canDistribute(nums, quantity);
        System.out.println(b);
    }

    public boolean canDistribute(int[] nums, int[] quantity) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.merge(num, 1, (a, b) -> a + b);
        }
        int size = map.size();
        int[] counts = new int[size];
        int index = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            counts[index++] = entry.getValue();
        }
        int length = 1 << quantity.length;
        boolean[][] arr = new boolean[size + 1][length];
        arr[0][0] = true;
        for (int i = 1; i <= size; i++) {
            int count = counts[i - 1];
            for (int j = 1; j < length; j++) {
                if (arr[i - 1][j] || getSum(j, quantity) <= count) {
                    arr[i][j] = true;
                    continue;
                }
                for (int k = 1; k < j; k++) {
                    if ((k | j) != j || !arr[i - 1][j - k] || getSum(k, quantity) > count) {
                        continue;
                    }
                    arr[i][j] = true;
                    break;
                }
            }
            if (arr[i][length - 1]) {
                return true;
            }
        }
        return arr[size][length - 1];
    }

    private int getSum(int k, int[] quantity) {
        int sum = 0;
        int index = 0;
        while (k != 0) {
            if ((k & 1) == 1) {
                sum += quantity[index];
            }
            k >>= 1;
            index++;
        }
        return sum;
    }

}
